//************************************************************
//    > File Name: merge-two-sorted-lists.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月21日 16:23:01
//***********************************************************
//lintcode #165
#include<bits/stdc++.h>
using namespace std;
class ListNode {
	public:
		int val;
		ListNode *next;
		ListNode(int val){
			this->val=val;
			this->next=NULL;
		}
};
ListNode *mergeTwoLists(ListNode *l1,ListNode *l2){
	ListNode H(-1),*p;
	for(p=&H;l1&&l2;p=p->next){
		if(l1->val < l2->val){
			p->next=l1;
			l1=l1->next;
		}else{
			p->next=l2;
			l2=l2->next;
		}
	}
	p->next = (l1?l1:l2);
	return H.next;
}
ListNode *create(vector<int> &v){
	ListNode H(-1),*p;
	int i=0;
	for(p=&H;i<v.size();++i){
		p->next=new ListNode(v[i]);
		p=p->next;
	}
	return H.next;
}
void clean(ListNode *l){
	for(ListNode *t;l;){
		t=l;
		l=l->next;
		delete t;
	}
}
int main(){
	vector<int> a={
		1,3,6,8
	};
	vector<int> b={
		1,2,5,9,10
	};
	ListNode *l1=create(a);
	for(ListNode *t=l1;t;t=t->next)
		cout<<t->val<<" ";
	cout<<endl;

	ListNode *l2=create(b);
	for(ListNode *t=l2;t;t=t->next)
		cout<<t->val<<" ";
	cout<<endl;

	ListNode *res=mergeTwoLists(l1,l2);
	for(;res;res=res->next)
		cout<<res->val<<" ";
	cout<<endl;
	clean(res);
}
